package com.cuz.daileetcode;


import javafx.util.Pair;

import java.util.TreeMap;

public class Day56 {


    static class TreePrintDirectory {
        /***
         * 前缀树节点定义
         */
        static class Node {
            /**
             * 当前路径
             */
            String curDir;
            /***
             * 此路径下的所有子路径
             */
            TreeMap<String, Node> subNode;

            public Node(String curDir, TreeMap<String, Node> subNode) {
                this.curDir = curDir;
                this.subNode = subNode;
            }
        }

        /***
         * 树形打印
         * @param dirArray 路径数组
         */
        static void solution1(String[] dirArray) {
            if (dirArray == null || dirArray.length == 0) {
                return;
            }
            //前缀树 头   可用理解为C盘
            Node root = new Node("", new TreeMap<>());
            //遍历每一个
            for (String temp : dirArray) {
                //当前路径的父节点
                Node upper = root;
                //分割每一个 loop是单个路径
                for (String loop : splitDir(temp)) {
                    //从父节点中拿当前路径的节点
                    Node curDirNode = upper.subNode.get(loop);
                    //不存在 那么建立一个
                    if (curDirNode == null) {
                        curDirNode = new Node(loop, new TreeMap<>());
                    }
                    //更新
                    upper.subNode.put(loop, curDirNode);
                    //更新 上层节点为当前节点
                    //   b//c//e 建立b后 d的父节点b
                    upper = curDirNode;
                }
            }
            //深度优先打印路径
            //不大于最顶层的节点 直接拿最顶层的子节点
            for (Node temp : root.subNode.values()) {
                depthFirstPrint(temp, 1);
            }
        }

        static String[] splitDir(String str) {
            if (str == null || str.length() == 0) {
                return new String[]{};
            }
            return str.split("\\\\");
        }

        /**
         * 第一层 0个空格
         * 第二层两个空格
         * 。。。
         * 空格= （level-1）*2
         *
         * @param node  需要打印的节点
         * @param level 当前层级
         */
        static void depthFirstPrint(Node node, int level) {
            if (node == null) {
                return;
            }
            System.out.println(spaceGenerate(level) + node.curDir);
            for (Node value : node.subNode.values()) {
                depthFirstPrint(value, level + 1);
            }
        }

        static String spaceGenerate(int level) {
            StringBuilder res = new StringBuilder();
            for (int num = 0; num < (level - 1) * 2; num++) {
                res.append(" ");
            }
            return res.toString();
        }

        public static void main(String[] args) {
            solution1(new String[]{"b\\cst", "d\\", "a\\d\\e", "a\\b\\ctg"});
        }
    }

    static class BinaryTreeConvertIntoLinkedList {

        /***
         * 二叉树节点定义
         */
        static class Node {
            String value;
            Node left;
            Node right;

            public Node(String value, Node left, Node right) {
                this.value = value;
                this.left = left;
                this.right = right;
            }
        }

        /***
         * 递归结果
         * 节点作为链表 的头和尾巴
         */
        static class Info {
            Node head;
            Node tail;

            public Info(Node head, Node tail) {
                this.head = head;
                this.tail = tail;
            }
        }

        static Info solution1(Node node) {
            if (node == null) {
                return null;
            }
            Info leftInfo = solution1(node.left);
            Info rightInfo = solution1(node.right);
            //当前这个节点的头和尾巴
            Node resHead = null;
            Node resTail = null;
            //左树不为null
            if (leftInfo != null) {
                //那么整棵树的头为左树的头
                resHead = leftInfo.head;
                //左树尾巴不为null 那么进行连接
                if (leftInfo.tail != null) {
                    leftInfo.tail.right = node;
                    node.left = leftInfo.tail;
                }
                //如果右树为null
                //那么整棵树的尾巴为当前节点node
                if (rightInfo == null) {
                    resTail = node;
                }
            }
            //如果右树不为null
            if (rightInfo != null) {
                //那么整个棵树的尾巴为右树尾巴
                resTail = rightInfo.tail;
                //右树头不为null 进行连接
                if (rightInfo.head != null) {
                    rightInfo.head.left = node;
                    node.right = rightInfo.head;
                }
                //如果左树为null 整颗树的头为当节点
                if (leftInfo == null) {
                    resHead = node;
                }
            }
            return new Info(resHead, resTail);
        }

    }


    static class MaximumBinarySearchSubtree {

        static class Node {
            int value;
            Node left;
            Node right;
        }

        /***
         * 树形dp结果
         */
        static class Info {
            /**
             * 数目最大的二叉搜索树的头节点
             * 是扩展了题目
             * 如果题目要求返回最大的二叉搜索树的头节点 那么需要这个参数
             */
            Node maxBstRoot;
            /**
             * 是否是二叉搜索树
             */
            boolean isBst;
            /***
             * 当前节点作为根节点子树最小
             */
            int min;
            /**
             * 当前节点作为根节点子树最大
             */
            int max;
            /***
             * 节点个数
             */
            int maxBstSize;

            public Info(Node maxBstRoot, boolean isBst, int min, int max, int maxBstSize) {
                this.maxBstRoot = maxBstRoot;
                this.isBst = isBst;
                this.min = min;
                this.max = max;
                this.maxBstSize = maxBstSize;
            }
        }

        static Info process(Node node) {
            //如果是叶子节点 basecase
            if (node == null) {
                return null;
            }
            Info leftInfo = process(node.left);
            Info rightInfo = process(node.right);
            Node maxBstRoot = null;
            boolean isBst = false;
            int maxBstSize = 0;
            int min = node.value;
            int max = node.value;
            //左树不为null
            if (leftInfo != null) {
                //当前树最小更新为左树最小
                min = Math.min(min, leftInfo.min);
                //当前树最大更新为左树最大
                max = Math.min(max, leftInfo.min);
                //情况1 不包括当前节点node自己 左树存在更新为左树
                maxBstRoot = leftInfo.maxBstRoot;
                maxBstSize = leftInfo.maxBstSize;
            }
            if (rightInfo != null) {
                min = Math.min(min, rightInfo.min);
                max = Math.min(max, rightInfo.min);
                //右树不为null 且右树节点数目大于左树 那么更新为右树
                //情况1 不包括当前节点node自己
                if (rightInfo.maxBstSize > maxBstSize) {
                    maxBstRoot = rightInfo.maxBstRoot;
                    maxBstSize = rightInfo.maxBstSize;
                }
            }
            //情况2 包括自己
            //要求左树是bst 右树是bst
            if (isBst(leftInfo) && isBst(rightInfo)) {
                //且要求自己的值大于左树最大 小于右树最小
                if (leftInfo == null || leftInfo.max < node.value) {
                    if (rightInfo == null || rightInfo.min > node.value) {
                        maxBstRoot = node;
                        isBst = true;
                        //最大节点个数就等于左树节点个数+右树节点个数+1
                        maxBstSize=1;
                        if (rightInfo!=null){
                            maxBstSize+=rightInfo.maxBstSize;
                        }
                        if (leftInfo!=null){
                            maxBstSize+=leftInfo.maxBstSize;
                        }
                    }
                }
            }
            return new Info(maxBstRoot,isBst,min,max,maxBstSize);
        }


        private static boolean isBst(Info info) {
            //空树视为二叉搜索树
            if (info == null) {
                return true;
            }
            //不为空就看具体是否是二叉搜索树
            return info.isBst;
        }
    }
}
